package com.algorithm.code.list;

/**
 * @description leetcode第160题，查找链表相交节点
 * @program: sudy
 * @description: leetcode第160题
 * @author:
 * @create: 2020-01-22 20:06
 **/
public class Leetcode160 {

    /**
     * @Description:获取两个链表的相交节点 1. 首先遍历两个链表获取两个链表的长度 A和B
     * 2. 长链表首先前移|A-B|步
     * 3. 同时遍历两个链表，比较节点；如果相同则返回
     * 4. 直到最后，如果没有则返回空
     * @Param: [nodeA, nodeB]
     * @return: com.algorithm.code.list.ListNode
     * @Author: kukuxiahuni
     * @Date: 2020/1/22
     */
    public ListNode getIntersectionNode(ListNode nodeA, ListNode nodeB) {

        if (nodeA == null || nodeB == null) {
            return null;
        }

        int sizeA = 0, sizeB = 0;
        ListNode p = nodeA, q = nodeB;
        while (p != null) {
            ++sizeA;
            p = p.next;
        }

        while (q != null) {
            ++sizeB;
            q = q.next;
        }

        /**
         * 指针归位
         */
        p = nodeA;
        q = nodeB;

        if (sizeA < sizeB) {
            p = nodeB;
            q = nodeA;
        }

        for (int i = 0; i < Math.abs(sizeA - sizeB); ++i) {
            p = p.next;
        }

        while (p != null && q != null) {
            if (p == q) {
                return p;
            }
            p = p.next;
            q = q.next;
        }
        return null;
    }

}
